On fast matrix-vector multiplication with a Hankel matrix in multiprecision arithmetics

摘要

We present two fast algorithms for matrix-vector multiplication $y=Ax$, where$A$ is a Hankel matrix. The current asymptotically fastest method is based onthe Fast Fourier Transform (FFT), however in multiprecision arithmetics withvery high accuracy FFT method is actually slower than schoolbook multiplicationfor matrix sizes up to $n=8000$. One method presented is based on adecomposition of multiprecision numbers into sums, and applying standard ordouble precision FFT. The second method, inspired by Karatsuba multiplication,is based on recursively performing multiplications with matrices of half-sizeof the original. Its complexity in terms of the matrix size $n$ is$\Theta(n^{\log 3})$. Both methods are applicable to Toeplitz matrices and tocirculant matrices.